针对大规模长序列无人机（UAV）影像定位中存在的速度慢、误差漂移等问题，结合UAV影像的特点，提出了一种基于场景图划分的UAV影像定位算法。首先，利用全球定位系统（GPS）辅助信息缩小特征匹配的空间搜索范围，从而加速同名点的提取；之后结合视觉一致性和空间一致性来构建场景图，并利用归一化割（Ncut）对其进行划分；接着，对各组场景图进行增量重建；最后，利用光束法平差（BA）融合场景图从而计算出场景的三维模型。此外，在BA阶段，所提算法对代价函数进行扩充，即加入了GPS空间约束信息。在四个UAV影像数据集上的实验结果表明，与COLMAP等多种运动恢复结构（SFM）算法相比，所提算法的定位速度提升了50%，重投影误差减小了41%，定位误差控制在0.5m之内。此外，通过有无GPS辅助下的算法的实验对比，可以得知引入相对和绝对GPS约束的BA有效解决了误差漂移问题，避免了出现歧义性结果，并且极大地减小了定位误差。